Parallelrechner: Wie macht man Computer schneller?

Parallelrechner: Wie macht man Computer schneller?

 

Während der massive Einsatz der Computertechnik in den verschiedensten Bereichen des täglichen Lebens für jedermann augenscheinlich ist, findet die Revolution in den wissenschaftlichen Labors eher im Stillen statt. Computer bilden inzwischen ein unverzichtbares Hilfsmittel in Forschung und Entwicklung. Diese Revolution ist möglich geworden durch eine neue Klasse von Hochleistungsrechnern, den massiv parallelen Systemen, deren Entwicklung in den Achtzigerjahren begann. Was noch vor wenigen Jahren die größten Computer auf Monate beschäftigt hätte, kann heute innerhalb von Stunden gerechnet werden. Mit der Steigerung der Leistungsfähigkeit von Rechensystemen erreicht man aber nicht nur, dass bereits vorhandene Aufgaben schneller durchgeführt werden, sondern — und dies ist der wirtschaftlich bedeutendere Effekt — es erschließen sich völlig neue Einsatzgebiete. So ist es in vielen Bereichen der Naturwissenschaft und der Technik inzwischen einfacher und ökonomischer, physikalische Vorgänge nicht mehr im direkten Experiment zu untersuchen, sondern sie in ein mathematisches Modell zu verpacken und mithilfe eines Hochleistungsrechners simulativ zu erforschen. Auf vielen Gebieten sind »echte« Experimente erst gar nicht möglich — Beispiele sind Kosmologie und Klimaforschung —, sodass hier Computersimulationen die einzig möglichen »Experimente« sind.

 

Die Simulation auf dem Rechner hat sich also in den Naturwissenschaften neben der theoretischen Analyse und dem praktischen Experiment als eine eigenständige dritte Methode etabliert.

 

Die Aussicht, zum Ende des Jahrtausends Supercomputer zur Verfügung zu haben, die in einer Sekunde Billionen von Fließkommaoperationen ausführen, beflügelt die Wissenschaftler und Ingenieure zu kühnen Träumen, was man damit in den verschiedenen Fachgebieten alles erreichen könne. Zahlreiche Memoranden wurden verfasst, und schließlich erkannten auch die staatlichen Stellen weltweit die Relevanz der Hochleistungsrechner für technische Innovationen und wirtschaftliche Konkurrenzfähigkeit und erklärten sie zur strategischen Angelegenheit hoher Priorität. In einem Report von 1993 sprach eine von der US-Regierung eingesetzte Expertenkommission von »Grand Challenges« (»großen Herausforderungen«) und definierte eine Reihe von Forschungsgebieten, in denen man sich durch Einsatz der schnellen Rechner große Durchbrüche erhoffte. Dazu zählen so verschiedene Probleme wie die Entschlüsselung menschlicher Gene, die Erklärung der Entstehung unseres Universums, die Vorhersage globaler Klimaveränderungen, die Entwicklung neuartiger Medikamente, die Entwicklung neuer Supraleiter und die Untersuchung biologischer Makromoleküle.

 

Nicht nur in der Grundlagenforschung, auch im Bereich der Produktentwicklung ist der Hochleistungsrechner ein bedeutender strategischer Faktor: Computersimulationen können dabei helfen, die Entwicklungszeit eines Produkts von der Idee bis zur Marktreife zu reduzieren. Beispiele hierfür sind die Crashanalyse von Kraftfahrzeugen, das Medikamentendesign in der Arzneimittelherstellung, strömungsmechanische Untersuchungen bei Fahrzeugen oder Flugzeugen und die Simulation elektronischer Schaltungen, beispielsweise von Speicher- und Prozessorchips.

 

Der Rechner hilft aber nicht nur, die erforderlichen Untersuchungen in geringer Zeit und zu geringeren Kosten durchzuführen, er hilft auch bei der Optimierung der Produkte, etwa bei der Minimierung des Materialaufwands unter gegebenen Festigkeitsanforderungen. In vielen Bereichen des Planens treten Optimierungsprobleme auf, bei denen ein Einsparungspotenzial in Milliardenhöhe vorhanden ist. Man denke an die Einsatzplanung von Flugzeugen und Crews bei großen Fluggesellschaften oder die Tourenplanung bei großen Speditionsunternehmen. Obwohl viele dieser Probleme auch für die derzeit schnellsten Rechner zu komplex sind, um die optimale Lösung zu finden, so kann man mit Rechnerhilfe durch geeignete heuristische Verfahren zumindest in die Nähe des Optimums gelangen. Supercomputer bilden innerhalb der Computertechnologie zwar nur ein sehr kleines Marktsegment, ihre Bedeutung für Wissenschaft und Technik kann jedoch kaum hoch genug eingeschätzt werden.

 

 Wie man Rechner schneller macht

 

Der Kern eines Rechners wird von zwei Komponenten gebildet, dem Prozessor, der als aktives Element einzelne Verarbeitungsschritte (Befehle) durchführt, und dem Hauptspeicher, in dem die einzelnen Verarbeitungsschritte als Programm sowie die zu verarbeitenden Daten abgelegt sind.

 

Alle Rechner arbeiten mit einem bestimmten Takt. In jedem Zyklus beschafft sich der Prozessor einen Befehl aus dem Speicher und führt ihn aus. Dazu muss er in der Regel weitere Daten aus dem Speicher holen oder aber Ergebnisse in den Speicher zurückschreiben. Ein solcher Befehlszyklus besteht aus mehreren Einzelschritten, die jeweils einen Takt lang sind. Die Taktrate oder Taktfrequenz wird dabei vorgegeben. Die maximale Taktfrequenz hängt von den internen Signallaufzeiten ab.

 

In den letzten Jahrzehnten sind die Einzelkomponenten — Prozessor und Speicher — ständig schneller geworden und haben so zur allgemeinen Leistungssteigerung beigetragen. Durch ständig verbesserte Technik konnten die Strukturen auf den Chips immer feiner werden, wodurch immer mehr Schaltkreise auf einem Chip integriert werden konnten. Bei Prozessoren erlaubt eine höhere Packungsdichte einerseits, mehr Transistoren und damit Funktionen auf derselben Chipfläche unterzubringen, andererseits werden durch dünnere Schichten die Schaltzeiten der Transistoren verkürzt, der Prozessor kann also mit einem höheren Takt betrieben werden. Die Dimension des Erreichten ist atemberaubend: Die meisten Prozessoren bestehen heute nur noch aus einem einzigen Chip; alle Funktionseinheiten dieses Mikroprozessors sind auf einem Halbleiterplättchen mit einer Kantenlänge von etwa zwei bis drei Zentimetern integriert. In den heutigen Prozessorchips liegen die Abmessungen der elementaren Strukturen bei 0,2 bis 0,3 Mikrometern; dies ist die Größenordnung der Länge eines DNA-Moleküls! Und bei Taktraten von 300 bis 800 Megahertz ergeben sich Prozessorzykluszeiten von wenigen Nanosekunden. Ein moderner Prozessor führt also einen Befehl aus, während ein Lichtstrahl gerade einen Meter zurücklegt! Die Anzahl der Transistoren auf einem Prozessorchip beträgt dabei einige Millionen.

 

Die einzelnen Komponenten des Rechners, also Prozessor und Speicher, haben an der allgemeinen Leistungssteigerung unterschiedlichen Anteil. So haben sich die Prozessorzykluszeiten in stärkerem Maße verkürzt als die Speicherzugriffszeiten. Die Zugriffszeiten auf den Hauptspeicher liegen typischerweise bei 10 bis 80 Nanosekunden; ein Speicherzugriff ist damit eine Größenordnung langsamer als ein Prozessorzyklus. Da ein Prozessor aber jeden Befehl aus dem Speicher holen muss, wird er durch einen langsamen Speicher gebremst. Der Prozessor würde daher die meiste Zeit untätig warten. Ein solches Auseinanderdriften der Leistungsfähigkeit der Komponenten erfordert Korrekturen in der Rechnerarchitektur, mit der die Geschwindigkeiten der Komponenten angepasst werden. So werden beispielsweise schnelle Pufferspeicher (Caches) zwischen Prozessor und Hauptspeicher eingefügt, deren Zugriffszeiten denen des Prozessors entsprechen. Sie sind im Vergleich zum Hauptspeicher teuer und werden daher klein dimensioniert. Durch geschickte organisatorische Maßnahmen gelingt es jedoch, dass die meisten Befehle und Daten sich in dem Moment, in dem der Prozessor sie benötigt, in diesem Pufferspeicher befinden, sodass nur in Ausnahmefällen direkt auf den Hauptspeicher zugegriffen werden muss.

 

 Ein schneller oder mehrere preisgünstige Prozessoren?

 

Die bisherige Entwicklung bei den Mikroprozessoren gehorchte der Regel, dass etwa alle 18 Monate eine Verdoppelung der Leistungsfähigkeit erreicht wird. Dieses nach dem Gründer der Firma Intel, Gordon Moore, benannte Moore'sche Gesetz zeigt mit erstaunlicher Präzision bereits seit 30 Jahren Gültigkeit. Jedoch wird innerhalb der nächsten zehn Jahre, wenn die Ladungskapazitäten die Größenordnung der Elementarladung und die Schichten die Stärke einer einzelnen Moleküllage erreichen, die Technik immer höherer Packungsdichte ausgereizt sein. Eine weitere Leistungssteigerung kann dann nur durch den gleichzeitigen Einsatz mehrerer Prozessoren erreicht werden.

 

Die triviale Erkenntnis, dass viele Prozessoren in gleicher Zeit mehr Arbeit leisten können als ein einzelner Prozessor, führte auch in der Vergangenheit schon zu Multiprozessorarchitekturen. Bereits der erste elektronische Digitalrechner aus dem Jahr 1942 war eine parallele Maschine. Die Parallelarchitektur geriet dann einige Jahre fast in Vergessenheit und wurde erst im Verlauf der Achtzigerjahre »wieder entdeckt«, wobei gleich mehrere Faktoren zu dieser Renaissance führten.

 

Erstens wurde absehbar, dass, wie oben bereits erwähnt, die physikalischen Grenzen weiterer Geschwindigkeitssteigerungen für die einzelnen Verarbeitungskomponenten bald erreicht sein würden. Zweitens haben die Fortschritte in der Chiptechnologie zu einer stärkeren Automatisierung der Produktion geführt, wodurch die Entwicklungskosten deutlich gesenkt werden konnten. Dies zusammen mit den sehr hohen Stückzahlen der Standard-Mikroprozessoren bewirkte einen rapiden Preisverfall. Die gleichzeitige Leistungssteigerung und Kostensenkung haben dann zwangsläufig die ökonomischen Grundregeln der Rechnerarchitektur auf den Kopf gestellt. Das altbekannte Grosch'sche Gesetz, nach dem der Preis eines Rechners mit der Quadratwurzel seiner Leistung steigt — ein doppelt so schneller Rechner wäre demnach billiger als zwei einfach schnelle — galt nun nicht mehr. Man konnte sich leicht ausrechnen, dass tausend zusammengeschaltete Mikroprozessoren die damaligen Einprozessorsuperrechner in ihrer Leistungsfähigkeit zumindest theoretisch übertreffen konnten, und dies bei einem Bruchteil des Herstellungspreises. Tatsächlich bestehen heutige Supercomputer aus Hunderten oder Tausenden konventioneller Mikroprozessoren, die zusammen eine Maschine bilden.

 

Ein Rechensystem besteht jedoch nicht nur aus der Maschine selbst, der Hardware, sondern ist nur zusammen mit den darauf ablaufenden Programmen, der Software, funktionsfähig. Erst das Zusammenspiel von Hard- und Software bestimmt die Leistungsfähigkeit der Maschine. Je geschickter die Software die vorhandenen Hardwareeigenschaften ausnutzt, desto besser ist die insgesamt erzielte Leistung. In den technischen Datenblättern von Computern wird die Rechenleistung oft in Form der Spitzenleistung (peak performance) dargestellt, die nur unter absolut idealer Programmausnutzung, also praktisch nie erzielt werden kann. Diese Spitzenleistung gibt man meistens als Anzahl der Fließkommaoperationen pro Sekunde (Flops) an, wobei die schnellsten Supercomputer bereits in der Teraflops-Klasse (10¹² Flops) liegen. Gerade bei Parallelrechnern ist es häufig nicht zu vermeiden, dass Programmteile auf Zwischenergebnisse anderer Programmteile warten und daher die betroffenen Prozessoren untätig auf der Stelle treten. So wird die potenziell vorhandene Leistung manchmal nur zu zehn bis zwanzig Prozent ausgeschöpft. Es sind daher organisatorische Maßnahmen erforderlich, die eine Nutzungsoptimierung der vorhandenen Komponenten zum Ziel haben. Gerade dieser Bereich macht das Programmieren für Parallelrechner oft beschwerlich, da die architektonischen Besonderheiten der jeweiligen Maschine im Programm berücksichtigt werden müssen. Während ein sequenzielles Programm in einer höheren Programmiersprache problemlos auf eine andere Maschine gebracht werden kann, müssen parallele Programme oft dem jeweiligen Parallelrechner auf den Leib geschnitten werden, um effizient abzulaufen. Da die Programme eine deutlich höhere Lebensdauer aufweisen als die sich schnell weiterentwickelnden Maschinen, meist also mehrere Rechnergenerationen überleben, müssen sie beim Übergang auf einen neuen Maschinentyp oftmals mit erheblichem Aufwand angepasst werden.

 

 Parallelarbeit im Computer

 

Parallelität bedeutet, dass mehrere Aktivitäten simultan ablaufen. In diesem Sinne ist Parallelität ein allgemeines Prinzip des Computers, das auf unterschiedlichen Ebenen und in sehr unterschiedlicher Weise in Rechensystemen eingesetzt werden kann. Daher kann das Attribut »parallel«, je nachdem, welche Ebene des Systems betrachtet wird, etwas grundsätzlich anderes bedeuten. Jede Ebene ist von spezifischen Operationen und Datenelementen geprägt.

 

Betrachten wir etwa die Ebene der elementaren Verarbeitungsschritte eines Rechners, beispielsweise das Schalten von Transistoren: Auf diesem Niveau verfügen auch konventionelle, sequenzielle Rechner über Parallelität. Ein Ausdruck für diese Eigenschaft eines Prozessors ist seine Verarbeitungsbreite, die angibt, wie viele elementare Dateneinheiten — Bits — auf einmal, also parallel, behandelt werden können. Die Bits bilden damit die Grundeinheiten der Datenverarbeitung. Zurzeit wird gerade der Wechsel von 32 Bit zu 64 Bit vollzogen.

 

Eine andere Form der Parallelität innerhalb eines Prozessors ist das mittlerweile übliche Fließbandprinzip, Pipelining genannt. Damit ist die überlappende Ausführung aufeinander folgender Befehle gemeint. Ähnlich wie Autos in einer Waschstraße werden die Befehle durch den Prozessor geschoben, sodass mehrere gleichzeitig in Bearbeitung sind. Darüber hinaus besitzen die jüngeren Prozessoren eine superskalare Architektur, sie verfügen über gleich mehrere Fließbänder, in denen unabhängige Befehlssequenzen simultan bearbeitet werden.

 

Dieses Prinzip kann aber nur dann funktionieren, wenn Befehle, die gleichzeitig in verschiedenen Fließbändern oder direkt nacheinander im selben Fließband ausgeführt werden, unabhängig voneinander sind. Benötigt ein Befehl als Eingabe einen Wert, der vom direkt vorangegangenen Befehl erst berechnet wird, so können diese beiden Befehle weder parallel noch direkt aufeinander folgend im Fließband bearbeitet werden. Es ist daher Aufgabe des Compilers, der aus dem Programmtext die Maschinenbefehle erzeugt, diese Maschinenbefehle so anzuordnen, dass möglichst viele von ihnen tatsächlich unabhängig sind; ein erheblicher Mehraufwand für den Compiler! Der Aufwand wird also von der Hardware in die Software verlagert.

 

Diese Formen der internen Parallelität sind bereits in heutigen Standardprozessoren in reichlichem Maß vorhanden. Trotzdem rechtfertigt dies nach allgemeinem Sprachgebrauch noch nicht die Bezeichnung »Parallelrechner«; man spricht erst dann von einem Parallelcomputer, wenn er über mehrere solcher Prozessoren verfügt.

 

Die prozessorinterne Parallelität vollzieht sich auf sehr feiner Ebene, die einzelnen simultan ausgeführten Aktivitäten — die Ausführung eines Maschinenbefehls oder eines Teils davon — spielen sich in sehr kurzen Zeiträumen ab. Parallelität zwischen den Prozessoren dagegen — und das ist die Domäne der Parallelrechner — ist naturgemäß etwas grobkörniger. Man spricht von der Granularität der Parallelverarbeitung, um anzugeben, wie groß die Programmstücke sind, die parallel zueinander bearbeitet werden.

 

 Warum Parallelverarbeitung?

 

Die Attraktivität der Parallelverarbeitung beruht auf der Vorstellung, dass ein Programm auf einem Parallelrechner mit 50 Prozessoren auch 50-mal schneller ausgeführt werden kann als auf einem konventionellen Einprozessorsystem. Diese Vorstellung könnte einen zu dem Irrglauben verleiten, man könne Programmlaufzeiten beliebig klein machen, indem man eine hinreichend große Prozessorzahl wählt. Dass dies und warum dies nicht so ist, soll kurz erläutert werden.

 

Man stelle sich vor, ein Arbeiter brauche eine Stunde, um mit einem Spaten eine Grube mit einem Meter Kantenlänge und einem Meter Tiefe auszuheben. Rein rechnerisch brauchen 1000 Arbeiter für diese Aufgabe 3,6 Sekunden. Dass dies Unsinn ist, bedarf wohl keiner besonderen Erwähnung. Besteht jedoch die Aufgabe darin, 1000 kleine Löcher mit je einem Kubikdezimeter Rauminhalt auszuheben, die über eine große Fläche verteilt sind, so kann die obige Rechnung durchaus realistisch sein. Obwohl in beiden Fällen der gleiche Rauminhalt auszuheben ist, gibt es im ersten Fall ein unbeschreibliches Gedränge mit gegenseitiger Behinderung, während im zweiten Fall die 1000 Arbeiter ungestört jeweils einen Spatenstich vornehmen können. Abgesehen von der Behinderung muss im Fall der Kubikmeter-Grube zuerst die oberste Schicht abgetragen sein, bevor die zweite Schicht in Angriff genommen werden kann. Es muss also eine Reihenfolge eingehalten werden, die verhindert, dass an jeder Stelle des Kubikmeters Erdreich gleichzeitig gearbeitet wird. Die erste Aufgabe ist eben nicht oder nur sehr begrenzt parallelisierbar — durch den Einsatz von zwei bis drei Arbeitern —, die zweite dagegen sehr gut parallelisierbar, allerdings auch nur bis zu tausend Grabern.

 

Durchaus ähnlich verhält es sich bei Parallelrechnern. Auch dort gibt es Aufgaben, die sich nahezu beliebig in parallele Teilaufgaben zerlegen lassen, und andere, bei denen eine umfangreiche Parallelisierung unmöglich ist oder zu ineffizientem Verhalten führt. Dabei sind es insbesondere die Abhängigkeiten zwischen den einzelnen Operationen, die eine sequenzielle Bearbeitung erzwingen und somit eine beliebige Parallelisierung verhindern. Als Maß für den Erfolg der Parallelisierung eines Programms gibt man meist den Speed-up an, das ist der erzielte Geschwindigkeitsgewinn beim Übergang von einem zu mehreren Prozessoren.

 

Bereits recht früh hat man Prognosen darüber aufgestellt, welche Beschleunigung denn durch Parallelrechner grundsätzlich zu erwarten sei. Die von Marvin Minsky, einem der Pioniere des Gebiets der »künstlichen Intelligenz«, 1971 geäußerte Vermutung, dass nur ein logarithmischer Speed-up — also Verdopplung der Geschwindigkeit bei Verzehnfachung der Prozessorzahl — erzielt werden könne, hat sich im Großen und Ganzen als zu pessimistisch erwiesen. Etwas präziser hat Gene Amdahl, einer der maßgeblichen Entwickler der legendären IBM-360-Großrechnerserie und spätere Gründer der Amdahl Corporation, bereits 1967 auf die Tatsache hingewiesen, dass auch hochgradig parallele Programme gewisse Anteile strenger Datenabhängigkeit aufweisen, die nur sequenziell ausgeführt werden können und daher den erzielbaren Speed-up grundsätzlich limitieren. Dieser Zusammenhang ist als Amdahl'sches Gesetz bekannt geworden.

 

Es lässt sich relativ einfach veranschaulichen: Ein Maß für die Effizienz der Parallelverarbeitung ergibt sich aus dem Verhältnis des Speed-up zu der Anzahl der eingesetzten Prozessoren. Wird beispielsweise eine Aufgabe durch den Einsatz eines Parallelrechners doppelt so schnell gelöst, so beträgt der Speed-up zwei. Enthält der Rechner drei Prozessoren, so ist die Effizienz der Parallelisierung 2/3. Eine Effizienz von eins entspricht einer idealen Situation, bei der durch die Parallelisierung keinerlei Verluste auftreten und alle Prozessoren voll genutzt werden können. Im Amdahl'schen Gesetz wird nun berücksichtigt, dass jedes Programm einen gewissen Anteil enthält, der nicht parallelisiert werden kann. Dieser Anteil braucht, unabhängig von der Zahl der Prozessoren, stets die gleiche Bearbeitungszeit. Selbst bei einer sehr großen Zahl paralleler Prozessoren kann das Programm also nicht schneller ablaufen als der sequenzielle Anteil der Aufgabe.

 

Der Speed-up kann auf zweierlei Weise interpretiert werden: Ein Speed-up von beispielsweise zehn heißt einerseits, dass eine gegebene Aufgabe zehnmal schneller gelöst wird, es kann aber auch bedeuten, dass eine zehnmal größere Aufgabe in gleicher Zeit gelöst werden kann. Man kann beispielsweise eine Million Adressen mit 16 Prozessoren zehnmal schneller durchsuchen als mit nur einem, oder in der Zeit, die der eine Prozessor für eine Million benötigt, mit 16 Prozessoren zehn Millionen Adressen durchsuchen, also eine zehnmal größere Aufgabe bearbeiten. Insofern scheint es offensichtlich klar zu sein, dass der Geschwindigkeitsfaktor (Speed-up) auch gleichzeitig ein Scale-up, ein Problemgrößenfaktor, ist.

 

Tatsächlich muss jedoch zwischen diesen beiden Größen feiner differenziert werden: John Gustafson, damals an den Sandia National Laboratories in San Diego, hat 1988 darauf hingewiesen, dass der Speed-up eigentlich nicht die in der Praxis relevante Größe ist. Parallelrechner werden meist nicht dazu genutzt, ein gegebenes Problem schneller zu lösen, sondern man will mit ihnen größere Aufgaben, die die Kapazität eines Ein-Prozessor-Rechners gesprengt hätten, in annähernd gleicher Zeit berechnen. Kurz gesagt: Man erwartet nicht das Gleiche in kürzerer Zeit, sondern mehr bei gleichem Zeitaufwand. Üblicherweise bleibt der sequenzielle Teil der Bearbeitung bei der Vergrößerung der Aufgabenstellung absolut gesehen konstant, während der parallele Anteil steigt. Da der Zeitaufwand für die Berechnung des parallelen Teils direkt von der Prozessorzahl abhängt, kann der Scale-up also im Prinzip beliebig groß werden. Legt man diese Interpretation zugrunde, so kann man die Aussichten der Parallelverarbeitung wesentlich optimistischer beurteilen als bei Amdahls Sichtweise.

 

Beide Ansätze ignorieren jedoch weitere Faktoren, die sich leistungsmindernd auswirken. So ist noch nicht die Tatsache berücksichtigt, dass die parallelen Programmteile miteinander kommunizieren müssen, um Zwischenergebnisse auszutauschen. Der zeitliche Aufwand für diese Kommunikation steigt in der Regel überproportional mit der Anzahl der Prozessoren, sodass die Speed-up-Kurve nicht nur nicht beliebig wächst, sondern sogar ein Maximum erreicht und wieder zu sinken beginnt. Eine zu starke Parallelisierung eines Programms kann demnach dazu führen, dass ein im Wesentlichen aus Kommunikation bestehender interner Aufwand den durch Parallelität entstandenen Gewinn mehr als aufwiegt.

 

Prof. Dr. Hans-Ulrich Heiss

 

Weiterführende Erläuterungen finden Sie auch unter:

 

Parallelrechner: Architekturen, Anwendungen, Entwicklungstrends

 

Literatur:

 

Huber, Walter: Paralleles Rechnen. München u. a. 1997.

 Ungerer, Theo: Parallelrechner und parallele Programmierung. Heidelberg u. a. 1997.

 Vollmar, Roland / Worsch, Thomas: Modelle der Parallelverarbeitung. Stuttgart 1995.